package demo5;
import java.util.*;
class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    //1.剑指 Offer II 025. 链表中的两数相加(栈+新链表)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //栈
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        //全都入栈
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        while(cur1 != null) {
            stack1.push(cur1);
            cur1 = cur1.next;
        }
        while(cur2 != null) {
            stack2.push(cur2);
            cur2 = cur2.next;
        }
        //进行计算
        ListNode head = null;
        int ans = 0;//控制进位
        while(!stack1.isEmpty() || !stack2.isEmpty()) {
            int a = stack1.isEmpty() ? 0 : stack1.pop().val;
            int b = stack2.isEmpty() ? 0 : stack2.pop().val;
            int sum = a + b + ans;
            ans = sum / 10;
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
        }
        if(ans == 1) {
            ListNode node = new ListNode(1);
            node.next = head;
            head = node;
        }
        return head;
    }

    //2.剑指 Offer II 022. 链表中环的入口节点
    public ListNode detectCycle(ListNode head) {
        //快慢指针，先找相遇点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        //排除没有环的情况
        if(fast == null || fast.next == null) {
            return null;
        }
        //一个指针从头开始走，另一个从相遇的点开始走，再次相遇一定就是入口点
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    //2.剑指 Offer II 022. 链表中环的入口节点(哈希法)
    public ListNode detectCycle(ListNode head) {
        //哈希表
        Set<ListNode> set = new HashSet<>();
        ListNode cur = head;
        while(cur != null) {
            if(set.contains(cur)) {
                return cur;
            }
            set.add(cur);
            cur = cur.next;
        }
        return null;
    }
    //3.交换链表中的节点(快慢指针)
    public ListNode swapNodes(ListNode head, int k) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur1 = head;
        ListNode cur2 = head;
        //找到第一个待交换的结点
        for(int i = 0; i < k - 1; i++) {
            cur1 = cur1.next;
        }
        //找到第二个待交换的结点(快慢指针)
        ListNode fast = cur1;//cur1是第一个待交换的结点
        while(fast.next != null) {
            fast = fast.next;
            cur2 = cur2.next;
        }
        //开始交换
        int tmp = cur1.val;
        cur1.val = cur2.val;
        cur2.val = tmp;
        return head;
    }

    //4.从链表中删去总和值为零的连续节点(前缀和问题)
    public ListNode removeZeroSumSublists(ListNode head) {
        //前缀和：一遍遍历一边记录和，若sum和之前的sum重复，就删除中间的
        ListNode cur = head;
        Map<Integer, ListNode> map = new HashMap<>();
        ListNode headNode = new ListNode(0, head);
        map.put(0, headNode);
        int sum = 0;
        while(cur != null) {
            sum += cur.val;
            //不包含就记录当前sum和结点
            if(!map.containsKey(sum)) {
                map.put(sum, cur);// (1,1),(3,2),(6,3),(3,-3),(1,-2)
            }else {
                //断开中间的结点
                ListNode node = map.get(sum);
                ListNode del = node.next;
                node.next = cur.next;
                //从map中删除
                int dSum = sum;//当前和也就是del那时的和，因为此时后面和为0
                while(del != cur) {
                    dSum += del.val;
                    map.remove(dSum);
                    del = del.next;
                }
            }
            cur = cur.next;
        }
        return headNode.next;
    }
    //5.删除链表的中间节点
    public ListNode deleteMiddle(ListNode head) {
        if(head == null || head.next == null) {
            return null;
        }
        //快慢指针
        ListNode headNode = new ListNode(0, head);
        ListNode prev = headNode;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        //进行删除
        prev.next = slow.next;
        return headNode.next;
    }
    //6.删除链表的中间节点(优化)
    public ListNode deleteMiddle(ListNode head) {
        if(head == null || head.next == null) {
            return null;
        }
        //快慢指针
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //进行删除
        slow.next = slow.next.next;
        return head;
    }
    //7.链表最大孪生和(快慢指针 + 栈)
    public int pairSum(ListNode head) {
        //快慢指针找到中间结点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow;
        //将后半部分入栈
        Stack<Integer> stack = new Stack<>();
        while(slow != null) {
            stack.push(slow.val);
            slow = slow.next;
        }
        //取出求和
        int max = Integer.MIN_VALUE;
        fast = head;
        while(fast != mid) {
            int sum = fast.val + stack.pop();
            max = sum > max ? sum : max;
            fast = fast.next;
        }
        return max;
    }

    //8.链表最大孪生和(快慢指针 + 反转链表)->更高效
    public int pairSum(ListNode head) {
        //快慢指针找到中间结点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转链表
        ListNode prev = null;
        ListNode cur = slow;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        //进行比较
        int max = Integer.MIN_VALUE;
        while(head != null && prev != null) {
            int sum = head.val + prev.val;
            max = sum > max ? sum : max;
            head = head.next;
            prev = prev.next;
        }
        return max;
    }
    //9.合并零之间的节点
    public ListNode mergeNodes(ListNode head) {
        ListNode cur = head;
        ListNode headNode = new ListNode();
        ListNode curNode = headNode;
        while(cur.next != null) {
            cur = cur.next;
            int sum = 0;
            //求两0之间的和
            while(cur.val != 0) {
                sum += cur.val;
                cur = cur.next;
            }
            ListNode node = new ListNode(sum);
            curNode.next = node;
            curNode = node;
        }
        return headNode.next;
    }
    //10.剑指 Offer II 119. 最长连续序列(哈希表超时)
    public int longestConsecutive(int[] nums) {
        //先用哈希法去重
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int max = 0;
        //寻找最长连续序列
        for(int num : set) {
            int sum = 1;
            while(set.contains(num += 1)) {
                sum++;
            }
            if(sum > max) {
                max = sum;
            }
        }
        return max;
    }
    //10.剑指 Offer II 119. 最长连续序列(优化)
    public int longestConsecutive(int[] nums) {
        //先用哈希法去重
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int max = 0;
        //寻找最长连续序列
        for(int num : set) {
            //不包含num - 1，相当于优化了，让他始终从第一个开始数
            if(!set.contains(num - 1)) {
                int sum = 1;
                while(set.contains(num += 1)) {
                    sum++;
                }
                if(sum > max) {
                    max = sum;
                }
            }
        }
        return max;
    }
}
